package practice;

import java.util.*;

public class Day19 {
    //飞地问题(多源dfs)
    //思路：反面考虑：把边界上的1（一定能出边界）全部先扔进队列，然后进行dfs
    private int[] dx = {0,0,1,-1};
    private int[] dy = {1,-1,0,0};
    public int numEnclaves(int[][] grid) {
        int count = 0;
        int size = 0;
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] flag = new boolean[m][n];
        Queue<Integer[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if((i == 0 || i == m-1 || j == 0 || j == n-1) && grid[i][j] == 1) {
                    queue.offer(new Integer[]{i,j});
                    count++;
                    flag[i][j] = true;
                }
                if(grid[i][j] == 1) {
                    size++;
                }
            }
        }

        while(!queue.isEmpty()) {
            Integer[] top = queue.poll();
            for(int i = 0; i < 4; i++) {
                int x = top[0] + dx[i];
                int y = top[1] + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && !flag[x][y] && grid[x][y] == 1) {
                    count++;
                    queue.offer(new Integer[]{x,y});
                    flag[x][y] = true;
                }
            }
        }
        return size-count;
    }
    //01矩阵
    //思路：也是从反面入手：先把0全部入队列，然后判断0的上下左右是否已经被标记过，然后进行dfs
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        Queue<Integer[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                dist[i][j] = -1;
                if(mat[i][j] == 0) {
                    queue.offer(new Integer[]{i,j});
                    dist[i][j] = 0;
                }
            }
        }
        while(!queue.isEmpty()) {
            Integer[] top = queue.poll();
            for(int i = 0; i < 4; i++) {
                int x = top[0] + dx[i];
                int y = top[1] + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] < 0 && mat[x][y] == 1) {
                    dist[x][y] = dist[top[0]][top[1]] + 1;
                    queue.offer(new Integer[]{x,y});
                }
            }
        }
        return dist;
    }
    //前k个高频单词
    //https://leetcode.cn/problems/top-k-frequent-words/
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(String s : words) {
            map.put(s,map.getOrDefault(s,0)+1);
        }
        PriorityQueue<String> queue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String i1, String i2) {
                if(map.getOrDefault(i1,0).compareTo(map.getOrDefault(i2,0)) == 0) {
                    return i2.compareTo(i1);
                }
                return map.getOrDefault(i1,0).compareTo(map.getOrDefault(i2,0));
            }
        });
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(queue.size() < k) {
                queue.offer(entry.getKey());
            }else {
                if(map.getOrDefault(entry.getKey(),0) > map.getOrDefault(queue.peek(),0)) {
                    queue.poll();
                    queue.offer(entry.getKey());
                }else if(map.getOrDefault(entry.getKey(),0) == map.getOrDefault(queue.peek(),0)) {
                    if(entry.getKey().compareTo(queue.peek()) < 0) {
                        queue.poll();
                        queue.offer(entry.getKey());
                    }
                }
            }
        }
        int i = 0;
        List<String> ret =  new LinkedList<>();
        while(!queue.isEmpty()) {
            ret.add(queue.poll());
        }
        Collections.reverse(ret);
        return ret;
    }
}
//数据流中第k大元素
//https://leetcode.cn/problems/kth-largest-element-in-a-stream/
class KthLargest {

    PriorityQueue<Integer> queue = null;
    int k = 0;

    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>(k);
        this.k = k;
        for(int x : nums) {
            queue.offer(x);
            if(queue.size() > k) {
                queue.poll();
            }
        }
    }

    public int add(int val) {
        queue.offer(val);
        if(queue.size() > k) {
            queue.poll();
        }
        return queue.peek();
    }
}
